/*
 * @Author: 缄默
 * @Date: 2021-11-11 20:28:45
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-11 21:48:48
 */

//派对的最大欢乐值

//实现本题的原因是顺便实现通过一个广度优先遍历重建整个树 这样测试的时候较为简单

//注意树形dp的思路 主要就是运用递归去求解 重点在于递归的返回如何写
//对于树来说 第一点就是空姐点如何返回 第二点就是如何用上一次返回值推出这一次的返回值
#include "../../DataStructure/tree.hpp"

using namespace std;

struct returnData {
    int yesHeadMax;
    int noHeadMax;
    returnData(int a, int b) : yesHeadMax(a), noHeadMax(b) { }
};

int getMaxHappy(TreeNode* head);
returnData* allTreeInfo(TreeNode* head);

int main() {
    vector<int> arr({4, 2, 1, 3, 6, 5, 7});
    TreeNode* head = buildTreeByArray(arr);
    cout << getMaxHappy(head) << endl;
    return 0;
}

int getMaxHappy(TreeNode* head) {
    return max(allTreeInfo(head)->yesHeadMax, allTreeInfo(head)->noHeadMax);
}

returnData* allTreeInfo(TreeNode* head) {
    if (head == nullptr) return new returnData(0, 0);
    returnData* left = allTreeInfo(head->left);
    returnData* right = allTreeInfo(head->right);
    int yes = head->val + left->noHeadMax + right->noHeadMax;
    int no = max(left->noHeadMax, left->yesHeadMax) + max(right->noHeadMax, right->yesHeadMax);
    return new returnData(yes, no);
}